import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2021-10-16
 * Time: 19:49
 */
public class MyPriorityQueue {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //建大堆，需要改变comparator参数
        PriorityQueue<List<Integer>>maxHeap=new PriorityQueue<>(new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                //如果o1减o2则默认是小堆
                return (o2.get(0)+o2.get(1))- (o1.get(0)+o1.get(1));
            }
        });
        for (int i = 0; i <Math.min(nums1.length,k) ; i++) {
            for(int j=0;j<Math.min(nums2.length,k);j++){
                if(maxHeap.size()<k) {
                    List<Integer> list=new ArrayList<>();
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    maxHeap.offer(list);
                }else{
                    //弹出堆顶的list元素的0下标和1下标的和跟剩下的两个数组里面的元素之和比较
                    int top=maxHeap.peek().get(0)+maxHeap.peek().get(1);
                    if(top>nums1[i]+nums2[j]){
                        //如果堆顶元素之和比数组元素之和的大，那么要弹出堆顶元素，把这两个数组元素包装成list,再把list放入大堆
                        maxHeap.poll();
                        List<Integer> list=new ArrayList<>();
                        list.add(nums1[i]);
                        list.add(nums2[j]);
                        maxHeap.offer(list);
                    }
                }
            }

        }
        //此时大堆里已经时和最小的K对数字了，但是要返回的是List嵌套类型，所以要把大堆的东西再一个个弹出来装入List
        List<List<Integer>> ret=new ArrayList<>();
        for (int i = 0; i < k && !maxHeap.isEmpty(); i++) {
            ret.add(maxHeap.poll());
        }
        return ret;
    }
}
